"Distance Estimation and Object Location via Rings of Neighbors"

We approach several problems on distance estimation and object location using a common technique called \emph{rings of neighbors}. Using this technique on metrics of low doubling dimension, we obtain significant improvements for low-stretch routing schemes, distance labeling, searchable small worlds, and triangulation-based distance estimation. Apart from improving the previously known bounds for these problems, our contributions include extending Kleinberg's small world model to metrics of low doubling dimension, and a short proof of the main result in [Chan et al., SODA'05]. Doubling dimension is a combinatorial (non-geometric) notion of dimensionality that has recently become popular in theoretical CS literature. A collection of rings of neighbors is a sparse distributed data structure that captures the distances and routing information. The idea is that every node $u$ stores pointers to some nodes called 'neighbors'; these pointers are partitioned into several 'rings', so that for some increasing sequence of balls $\{B_i\}$ around $u$, the neighbors in the $i$-th ring lie inside $B_i$; the radii of these balls and the distribution of neighbors in a given ring depend on the specific application. For metrics of low doubling dimension it has been particularly helpful to combine the following two collections of rings: in the first collection, the cardinalities of the balls $B_i$ grow exponentially, and the neighbors are distributed randomly; in the second collection the \emph{radii} of the $B_i$'s grow exponentially, and the neighbors are distributed geographically. Although used implicitly in several contexts, rings of neighbors have not been articulated as a general proof technique